It is normal for a data processing system to support many data entities or files called for by the potential user by identity whereas the data processing system needs to know the address, usually in peripheral storage, at which the data entity or at least the start of the data entity is stored. Since the system allocates storage, the system also maintains an index in which it records the addresses at which it has stored data entities in association with the identities of those data items. In other words, an index is a machine maintained mapping of data identity onto data location. The main function performed in relation to an index is searching and to speed searching, hierarchical indices are normal in systems of any appreciable capacity. In a hierarchical index, there are plural sequential levels of mapping extending from an entry level or apex to an exit level or base. Each level maps onto the next sequential level so that the extent of the next level requiring processing during a search is limited.
However, alteration of a hierarchical index is much more time consuming than is alteration of the equivalent single level index since, again in the worst case, an alteration, always at the base level, may propagate "upwards" through all the levels up to and including the apex. Conventionally, the index is not available for its main function--searching--while it is being updated and its integrity is not maintained, if it is not maintained updated. Further, updating by insertion and deletion tends to create a most irregular index structure, and it is the function of the upkeep macro operation--compression--to restore, periodically, the regularity of the index structure. Compression is the most time consuming of the upkeep operations. For examples of conventional hierarchical index upkeep operations, please refer to:
U.S. Pat. No. 3,643,226 PA1 U.S. Pat. No. 3,611,316 PA1 U.S. Pat. No. 3,916,316 PA1 U.S. Pat. No. 3,651,483 PA1 UK Pat. No. 1,336,817
Ideally we would like to provide a hierarchical index which can be searched while it is being updated. Although we have not succeeded in achieving this end in absolute terms, we have devised an index which can
(a) be searched at virtually any point during compression of the index,
(b) be updated by insertion or deletion at regularly ocurring break points during compression of the index and
(c) accommodate compression restart at the point at which it was interrupted.
It is pointed out that an approach to these aims can be achieved by duplicating the index in such a way that one copy of the index is available for searching, insertion and deletion; while the other copy is being compressed, but this arrangement, apart from absorbing storage space, implies that neither copy is fully maintained.
In the case of the present invention, there is no duplication and the single index is, in terms, fully maintained.